﻿#pragma once
#include "stdafx.h"
#include <initializer_list>
#include <functional>


//给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。
//你可以假设除了数字 0 之外，这两个数字都不会以零开头。
//
//进阶：
//如果输入链表不能修改该如何处理？换句话说，你不能对列表中的节点进行翻转。
//
//示例：
//输入：(7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
//输出：7 -> 8 -> 0 -> 7
//
//来源：力扣（LeetCode）
//链接：https ://leetcode-cn.com/problems/add-two-numbers-ii
//著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

class Solution {
public:
	string ListToString(ListNode* l)
	{
		string res;
		ListNode* p = l;
		while (p != nullptr)
		{
			res.push_back(p->val + '0');
			p = p->next;
		}
		return res;
	}

	ListNode* StringToList(const string& str)
	{
		ListNode* pHead{};
		ListNode* pTail{};
		for (const auto& ch : str)
		{
			ListNode* pNode = new ListNode(ch - '0');
			if (pHead == nullptr)
				pHead = pNode;
			else
				pTail->next = pNode;
			pTail = pNode;
		}
		return pHead;
	}

	void StringRevert(string& str)
	{
		for (size_t i = 0; i < str.size() / 2; i++)
		{
			//交换str[i]和str[str.size()-i-1]
			char ch = str[i];
			str[i] = str[str.size() - i - 1];
			str[str.size() - i - 1] = ch;
		}
	}

	string AddTowStrings(string str1, string str2)
	{
		string sum;
		StringRevert(str1);
		StringRevert(str2);
		if (str1.size() > str2.size())
		{
			str2.resize(str1.size(), '0');
			sum.resize(str1.size() + 1, '0');
		}
		else if (str1.size() < str2.size())
		{
			str1.resize(str2.size(), '0');
			sum.resize(str2.size() + 1, '0');
		}
		else
		{
			sum.resize(str1.size() + 1, '0');
		}
		str1.resize(str1.size() + 1, '0');
		for (size_t i = 0; i < sum.size() - 1; i++)
		{
			if (str1[i] - 48 + str2[i] - 48 < 10)        //如果当前位数相加没有进位
			{
				sum[i] = str1[i] - 48 + str2[i];    //和的当前位置即为两个加数当前位数相加
			}
			else
			{
				sum[i] = (str1[i] - 48 + str2[i] - 48) % 10 + 48;    //有进位，和的当前位数为两个加数相加对10取余
				str1[i + 1]++;        //加数的前一位数进位
			}
		}
		sum[str1.size() - 1] += (str1[str1.size() - 1] - 48);		//如果加数最高一位有进位，把它加到和的该位上
		int zero_count = 0;
		for (size_t i = sum.size() - 1; i > 0; i--)        //从最高位开始统计0的个数
		{
			if (sum[i] == '0') zero_count++;		//检测到0，zero_count就自加
			else break;		//一旦不是0就退出循环
		}
		sum.resize(sum.size() - zero_count);    //删除高位上的0
		StringRevert(sum);        //把sum变为正常顺序
		return sum;
	}

	ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
		string str1 = ListToString(l1);
		string str2 = ListToString(l2);
		string sum = AddTowStrings(str1, str2);
		return StringToList(sum);
	}

};

void Test()
{
	Solution solution;
	ListNode* pNode = solution.StringToList("1234");
	string str = solution.ListToString(pNode);

	string sum = solution.AddTowStrings("7243", "564");

	int a = 0;
}